The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Example 1:
Input: n = 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 9
Average Rating: 4.93 (14 votes)
Solution
Overview
A brute force solution would involve generating all possible board states with N queens. There are N2 possible squares to place the first queen, N2−1 to place the second and so on. This leads to a time complexity of O(NN), which is far too slow. The actual number of solutions is way smaller than the number of possible board states, so we should aim to minimize our consideration of invalid board states.
Imagine if we tried to generate all board states by placing queens down one by one. For 8 queens on a normal chessboard, let's say we place the first queen on the top left (index (0, 0), or, if you are familiar with Chess, a8). Then, we place the second queen to its right (index (0, 1), or b8).
There are 44,261,653,680 possible ways to place the remaining 6 queens, but we already know that every single one of them is invalid, because the first 2 queens can attack each other.
Approach: Backtracking
Intuition
We can still follow the strategy of generating board states, but we should never place a queen on an attacked square. This is a perfect problem for backtracking - place the queens one by one, and when all possibilities are exhausted, backtrack by removing a queen and placing it elsewhere.
If you're not familiar with backtracking, check out the backtracking section of our Recursion II Explore Card.
Given a board state, and a possible placement for a queen, we need a smart way to determine whether or not that placement would put the queen under attack. A queen can be attacked if another queen is in any of the 4 following positions: on the same row, on the same column, on the same diagonal, or on the same anti-diagonal.
Recall that to implement backtracking, we implement a backtrack function that makes some changes to the state, calls itself again, and then when that call returns it undoes those changes (this last part is why it's called "backtracking").
Each time our backtrack function is called, we can encode state in the following manner:
-
To make sure that we only place 1 queen per row, we will pass an integer argument
rowintobacktrack, and will only place one queen during each call. Whenever we place a queen, we'll move onto the next row by callingbacktrackagain with the parameter valuerow + 1. -
To make sure we only place 1 queen per column, we will use a set. Whenever we place a queen, we can add the column index to this set.
The diagonals are a little trickier - but they have a property that we can use to our advantage.
- For each square on a given diagonal, the difference between the row and column indexes
(row - col)will be constant. Think about the diagonal that starts from(0, 0)- the ith square has coordinates(i, i), so the difference is always 0.
- For each square on a given anti-diagonal, the sum of the row and column indexes
(row + col)will be constant. If you were to start at the highest square in an anti-diagonal and move downwards, the row index increments by 1(row + 1), and the column index decrements by 1(col - 1). These cancel each other out.
Whenever we place a queen, we should calculate the diagonal and the anti-diagonal value it belongs to. In the same way we had a set for the column, we should also have a set for both the diagonals and anti-diagonals. Then, we can put the values for this queen into the corresponding sets. Then, we can put the values for this queen into the corresponding sets.
Algorithm
We'll create a recursive function backtrack that takes 4 arguments to maintain the board state. The first parameter is the row we're going to place a queen on next, and the other 3 are sets that track which columns, diagonals, and anti-diagonals have already had queens placed on them. The function will work as follows:
-
If the current row we are considering is greater than
n, then we have a solution. Return1. -
Initiate a local variable
solutions = 0that represents all the possible solutions that can be obtained from the current board state. -
Iterate through the columns of the current row. At each column, we will attempt to place a queen at the square
(row, col)- remember we are considering the current row through the function arguments.- Calculate the diagonal and anti-diagonal that the square belongs to. If there has been no queen placed yet in the column, diagonal, or anti-diagonal, then we can place a queen in this column, in the current row.
- If we can't place the queen, skip this column (move on to try with the next column).
-
If we were able to place a queen, then update our 3 sets (
cols,diagonals, andantiDiagonals), and call the function again, but withrow + 1. -
The function call made in step 4 explores all valid board states with the queen we placed in step 3. Since we're done exploring that path, backtrack by removing the queen from the square - this just means removing the values we added to our sets.
Implementation
Complexity Analysis
-
Time complexity: O(N!), where N is the number of queens (which is the same as the width and height of the board).
Unlike the brute force approach, we place a queen only on squares that aren't attacked. For the first queen, we have N options. For the next queen, we won't attempt to place it in the same column as the first queen, and there must be at least one square attacked diagonally by the first queen as well. Thus, the maximum number of squares we can consider for the second queen is N−2. For the third queen, we won't attempt to place it in 2 columns already occupied by the first 2 queens, and there must be at least two squares attacked diagonally from the first 2 queens. Thus, the maximum number of squares we can consider for the third queen is N−4. This pattern continues, giving an approximate time complexity of N! at the end.
-
Space complexity: O(N), where N is the number of queens (which is the same as the width and height of the board).
Extra memory used includes the 3 sets used to store board state, as well as the recursion call stack. All of this scales linearly with the number of queens.
April 10, 2021 5:05 PM
Nice editorial with proper steps.
May 26, 2021 2:07 AM
I solved both these two LC HARD N-queen problems (after understanding solution of 1 obv), but I feel so happy.
Keep going
May 1, 2021 9:54 PM
pls explain how come time complexity is 0(N pow N) for brute force unable to understand
It would be nice if the definition of "distinct" was included. I thought it meant fundamental (eliminating rotate and flip).
Very elegant solution with a great explanation. Thank you!
May 29, 2021 10:25 PM
It's one of my favorite backtrack problems. The diagonal and anti-diagonal trick is brilliant!
May 29, 2021 7:45 PM
Thank you for choosing N-Queue again for this week. That will save us a lot of time to study the question and we will have more fun in Memorial Day. I can feel your consideration. Thank you.
May 1, 2021 10:43 PM
nice clear solution
class Solution:
def totalNQueens(self, n: int) -> int:
total = 0
def is_safe_to_place(sol: List[List[bool]], row: int, col: int) -> bool:
# 1.Check left
for i in range(col):
if sol[row][i]: return False
# 2.Check left up diag
i, j = row, col
while i > -1 and j > -1:
if sol[i][j]: return False
j -= 1
i -= 1
# 3.Check left down diag
i, j = row, col
while i < len(sol) and j > -1:
if sol[i][j]: return False
j -= 1
i += 1
return True
def backtrack(sol: List[List[bool]], col: int, n: int) -> int:
nonlocal total
if col == n:
total += 1
for row in range(n):
if is_safe_to_place(sol, row, col):
sol[row][col] = True
if backtrack(sol, col+1, n):
total += 1
sol[row][col] = False
sol = [[False] * n for _ in range(n)]
backtrack(sol, 0, n)
return total
xxxxxxxxxxclass Solution {public: int totalNQueens(int n) { }};